package TwoPointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Author: Darven
 * @CreateTime: 2025-03-30  21:24
 * @Description: TODO
 */
public class P15 {
    public static void main(String[] args) {
        int[] nums={0,0,0};
        P15Demo p15Demo = new P15Demo();
        System.out.println(p15Demo.threeSum(nums).toString());;
    }
}

class P15Demo {
    /**
     * 解题思路：通过排序，然后用双指针查找
     * 难点：重复元素去除，自己要想好久，其实将数组画一下就好啦
     * 时间复杂度 O(n*2)
     * */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans=new ArrayList<>();
        int length=nums.length;
        // 长度减2 留给l和r空间
        for(int i=0;i<length-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int l=i+1;
            int r= length-1;
            while(l<r){
                List<Integer> list=null;
                if(nums[i]+nums[l]+nums[r]==0){
                    list = List.of(nums[l], nums[r], nums[i]);
                    ans.add(list);
                    //去掉相同的
                    //注意数组越界问题  l<length-1  r>i
                    while(l<length-1&&nums[l]==nums[l+1]){
                        l++;
                    }
                    while(r>i&&nums[r]==nums[r-1]){
                        r--;
                    }
                }
                //如果指针数之和大于i的话，r要左移
                if((-nums[i])<(nums[l]+nums[r])){
                    r--;
                }
                else{
                    l++;
                }

            }
        }
        return ans;
    }
}
